#include "headfiles.h"

using namespace std;

int findElemRecur(int *array, int start, int end, int elem) {
    if (array == NULL) {
        cout << "Invalid input argument!" << endl;
        return -1;
    }

    if (start >= end) {
        return -1;
    }

    int mid_loc = (start + end) / 2;
    if (array[mid_loc] == elem) {
        return mid_loc;
    }
    else if (array[mid_loc] < elem) {
        start = mid_loc + 1;
    }
    else {
        end = mid_loc;
    }

    return findElemRecur(array, start, end, elem);
}

int findElem0(int *array, int elem_num, int elem) {
    return findElemRecur(array, 0, elem_num, elem);
}

int findElem1(int *array, int elem_num, int elem) {
    if (array == NULL ||
        elem_num <= 0) {
        cout << "Invalid input argument!" << endl;
        return -1;
    }

    int l = 0;
    int r = elem_num;
    int mid_loc;

    while (l < r) {
        mid_loc = (l + r) / 2;
        if (array[mid_loc] == elem) {
            return mid_loc;
        }
        else if (array[mid_loc] < elem) {
            l = mid_loc + 1;
        }
        else {
            r = mid_loc;
        }
    }

    return -1;
}

int findElem(int *array, int elem_num, int elem) {
    if (array == NULL ||
        elem_num <= 0) {
        cout << "Invalid argument!" << endl;
        return -1;
    }

    int start = 0;
    int end = elem_num;
    int mid_loc;

    while (start < end) {
        mid_loc = (start + end) / 2;
        if (array[mid_loc] == elem) {
            return mid_loc;
        }
        else if (array[mid_loc] < elem) {
            if (array[mid_loc] <= array[start]) {
                if (elem > array[end - 1]) {
                    end = mid_loc;
                } 
                else {
                    start = mid_loc + 1;
                }
            }
            else {
                start = mid_loc + 1;
            }
        }
        else {
            if (array[mid_loc] <= array[start]) {
                end = mid_loc;
            }
            else {
                if (elem < array[start]) {
                    start = mid_loc + 1;
                }
                else {
                    end = mid_loc;
                }
            }
        }
    }

    return -1;
}

